package com.example.origin.demo.suanfa.advanced;

import java.util.Arrays;

/**
 * @Description 研究kmp算法
 * @author daixiaoyong
 * @date 2019年3月6日 下午5:10:30
 */
public class StringKmp {
 
	/**
	 * 用于计算匹配的位置（从头到尾）
	 * 
	 * @param str
	 * @param sub
	 * @return
	 */
//	public static int kmp(String str, String sub) {
//		if (str == null || sub == null || str.length() == 0 || sub.length() == 0)
//			throw new IllegalArgumentException("str或者sub不能为空");
//		int[] n = next(sub);
//		for (int i = 0,j = 0; i < str.length(); i++) {
//			while (j > 0 && str.charAt(i) != sub.charAt(j)) j = n[j - 1];
//			if (str.charAt(i) == sub.charAt(j)) j++;
//			if (sub.length() == j) return i - j + 1;
//		}
//		return -1;
//	}

	public static int kmp(String str, String sub) {
		int length = sub.length();
		int arr[] = new int[length];
		for (int i = 0, j = 0; i < str.length(); i++) {
			while (j>0&&sub.charAt(j)!=str.charAt(i))j = arr[j-1];
			if(sub.charAt(j)==str.charAt(i))j++;
			if (length == j) return i-j+1;
		}
		return -1;
	}
 
	/**
	 * 用于生成部分匹配表
	 * 
	 * @param sub
	 * @return
	 */
//	public static int[] next(String sub){
//		int[] next = new int[sub.length()];
//		for(int i = 1,j = 0; i < sub.length(); i++){
//			while(j > 0 && sub.charAt(j) != sub.charAt(i)){
//				j = next[j - 1];
//				System.out.println(sub.charAt(i));
//			}
//			if(sub.charAt(i) == sub.charAt(j))j++;
//				next[i] = j;
//		}
//		return next;
//	}

	public static int[] next(String sub){
		int size = sub.length();
		int arr[] = new int[size];
		for (int i = 1,j = 0; i < size; i++) {
			while (j>0&&sub.charAt(j)!=sub.charAt(i))j = arr[j-1];
			if(sub.charAt(j)==sub.charAt(i))j++;
			arr[i] = j;
		}
		return arr;
	}

	public static void main(String[] args) {
		String str = "11514257518514252547";
		String sub = "5185142";
		System.out.println(Arrays.toString(next(sub)));
		int index = kmp(str, sub);
		System.out.println("index-->" + index);
	}
}
